package com.topcoder.tccc04;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class DataFilter {
	private ArrayList<Record>	INA;
	private ArrayList<Record>	IN;
	private ArrayList<Record>	IA;
	private ArrayList<Record>	NA;
	private ArrayList<Record>	I;
	private ArrayList<Record>	N;
	private ArrayList<Record>	A;
	
	public int untangle(String[] data) {
		int total = 0;
		ArrayList<Record> rs = new ArrayList<Record>();
		try {
			for (String row : data) {
				for (String record : row.split(";")) {
					addRecord(record, rs);
				}
			}
		} catch (Exception e) {
			return -1;
		}
		
		// 1. merge partial records to full record, by I
		ArrayList<Record> rs2 = new ArrayList<Record>();
		for (Record r : rs) {
			merge(r, rs2);
		}
		
		// 2. classify remaining records to 7 categories
		classify(rs2);
		total += INA.size();
		
		// 3. Tweaked max flow
		total += maxFlow();
		
		// 4. match remaining singles (I/N/A)
		total += IN.size();
		int maxSingle = Math.max(0, A.size() - IN.size());
		
		total += IA.size();
		maxSingle = Math.max(maxSingle, Math.max(0, N.size() - IA.size()));
		
		total += NA.size();
		maxSingle = Math.max(maxSingle, Math.max(0, I.size() - NA.size()));
		
		return total + maxSingle;
	}
	
	// map {IN, IA} to {NA}
	private int maxFlow() {
		boolean[][] bp = new boolean[NA.size()][IN.size() + IA.size()];
		for (int i=0; i<NA.size(); i++) {
			Record na = NA.get(i);
			for (int j=0; j<IN.size(); j++) {
				if (na.name.equals(IN.get(j).name)) bp[i][j] = true;
			}
			for (int j=0; j<IA.size(); j++) {
				if (na.age.equals(IA.get(j).age)) bp[i][j + IN.size()] = true;
			}
		}
		
		int[] match = new int[NA.size()];
		boolean[] visited = new boolean[NA.size()];
		for (int i=0; i<NA.size(); i++) match[i] = -1;
		
		int balance = N.size() - A.size();
		int i = 0, j = 0;
		while (i<IN.size() || j<IA.size()) {
			for (int k=0; k<NA.size(); k++) visited[k] = false;
			if ((balance >= 0 && i<IN.size()) || j==IA.size()) {
				dfs(i, bp, match, visited);
				i++;
			}
			else {
				dfs(j+IN.size(), bp, match, visited);
				j++;
			}
		}
		
		int res = 0;
		HashSet<Record> sub = new HashSet<Record>();
		for (i=0; i<NA.size(); i++) {
			if (match[i] >= 0) {
				res++;
				sub.add(NA.get(i));
				sub.add(match[i] < IN.size()? IN.get(match[i]) : IA.get(match[i] - IN.size()));
			}
		}
		
		NA.removeAll(sub);
		IN.removeAll(sub);
		IA.removeAll(sub);
		
		return res;
	}
	
	private int dfs(int i, boolean[][] bp, int[] match, boolean[] visited) {
		if (i == -1) return 1;
		for (int j=0; j<match.length; j++) {
			if (bp[j][i] && !visited[j]) {
				visited[j] = true;
				if (dfs(match[j], bp, match, visited) > 0) {
					match[j] = i;
					return 1;
				}
			}
		}
		return 0;
	}
	
	private void classify(ArrayList<Record> rs) {
		INA = new ArrayList<Record>();
		IN = new ArrayList<Record>();
		IA = new ArrayList<Record>();
		NA = new ArrayList<Record>();
		I = new ArrayList<Record>();
		N = new ArrayList<Record>();
		A = new ArrayList<Record>();
		
		for (Record r : rs) {
			if (r.id != null && r.name != null && r.age != null) {
				INA.add(r);
			}
			else if (r.id != null && r.name != null) {
				IN.add(r);
			}
			else if (r.id != null && r.age != null) {
				IA.add(r);
			}
			else if (r.age != null && r.name != null) {
				NA.add(r);
			}
			else if (r.id != null) {
				I.add(r);
			}
			else if (r.name != null) {
				N.add(r);
			}
			else {	// r.age != null
				A.add(r);
			}
		}
	}
	
	private void merge(Record r, ArrayList<Record> rs2) {
		for (Record r2 : rs2) {
			if (compatible(r, r2) || compatible(r2, r)) {
				r2.id = or(r2.id, r.id);
				r2.name = or(r2.name, r.name);
				r2.age = or(r2.age, r.age);
				return;
			}
		}
		rs2.add(r);
	}
	
	private String or(String s1, String s2) {
		return s1!=null? s1 : s2;
	}
	
	private boolean compatible(Record r, Record r2) {
		return compatible(r.id, r2.id) && compatible(r.name, r2.name) 
				&& compatible(r.age, r2.age);
	}
	
	private boolean compatible(String s1, String s2) {
		return s2==null || (s1!=null && s1.equals(s2));
	}
	
	private void addRecord(String r, ArrayList<Record> rs) throws Exception {
		StringTokenizer st = new StringTokenizer(r, " ");
		String id = null, name = null, age = null;
		while (st.hasMoreElements()) {
			String s = (String) st.nextElement();
			if (s.startsWith("0")) {
				id = s;
			}
			else if (s.matches("\\d*")) {
				age = s;
			}
			else {
				name = s;
			}
		}
		Record record = findRecordByID(id, rs);
		if (record == null) {
			rs.add(new Record(id, name, age));
			return;
		}
		
		if (record.name == null) {
			record.name = name;
		}
		else if (name!=null && !record.name.equals(name)) throw new Exception("Contradict");
				
		if (record.age == null) {
			record.age = age;
		}
		else if (age!=null && !record.age.equals(age)) throw new Exception("Contradict");
	}
	
	private Record findRecordByID(String id, ArrayList<Record> rs) {
		if (id == null) return null;
		for (Record record : rs) {
			if (id.equals(record.id)) return record;
		}
		return null;
	}
	
	private class Record {
		String id, name, age;
		public Record(String id, String name, String age) {
			this.id = id;
			this.name = name;
			this.age = age;
		}
	}
}
